package mo.tags.stack;

import java.util.Stack;

public class L1856 {

    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        long[] preSum = new long[n+1];
        for (int i = 0; i < n; i++) {
            preSum[i+1] = preSum[i] + nums[i];
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        long mode = 1000000007;
        long ans = 0;
        int i = 0;
        while (i <= n) {
            while (stack.peek() != -1 && (i == n || nums[stack.peek()] > nums[i])) {
                int min = nums[stack.pop()];
                ans = Math.max(ans, (long) min * (preSum[i]-preSum[stack.peek()+1]));
            }
            stack.push(i);
            i++;
        }
        return (int) (ans % mode);
    }

}
